package offer

import (
	. "GoLeetcode/common"
	"math"
	"sort"
)

/*
时间复杂度:O(N)
空间复杂度:O(1)

f1:滑动窗口
*/

func minSubArrayLen(target int, nums []int) int {
	left, right := 0, 0
	n := len(nums)
	sum := 0
	ansLen := math.MaxInt32
	for right < n {
		sum += nums[right]
		for sum >= target {
			ansLen = Min(ansLen, right-left+1)
			sum -= nums[left]
			left++
		}
		right++
	}
	if ansLen == math.MaxInt32 {
		return 0
	}
	return ansLen
}

/*
时间复杂度:O(NlogN) 二分查找logN，遍历N次 => NlogN
空间复杂度:O(N) 用来存储前缀和的切片长度

f2:前缀和+二分查找

1.题目给的条件是所有元素>=1, 即前缀和一定是一个递增的序列
2.题目要求的是一个满足条件的序列Sum(nums[i+1....j]) >= target;假设preSum[i]表示 Sum(nums[0...i-1])
preSum[j] - preSum[i] => Sum(nums[i+1...j])

转换为:
preSum[j] - preSum[i] >= target  => preSum[i] + target <= preSum[j] 即求preSum[j]>=target+preSum[i]且j>i的最小的j
这样可以使得最终的序列长度最小

而由于preSum是一个递增序列, preSum[i]+target (target>=1) 的值设置x, 在preSum中可以通过二分找到大于等于x且索引最小的序列
*/
func minSubArrayLen1(target int, nums []int) int {
	n := len(nums)
	preSum := make([]int, n+1)
	// preSum[i]表示 nums[0...i-1]的前缀和
	for i := 1; i <= n; i++ {
		preSum[i] = preSum[i-1] + nums[i-1]
	}

	ans := math.MaxInt32
	// 注意，这里必须从0开始遍历，因为当nums[0...n-1]的和为target时，target+preSum[0] == preSum[n],所以一定要遍历到preSum[0]
	for i := 0; i <= n; i++ {
		t := target + preSum[i]
		// 美[baʊnd]
		bound := sort.SearchInts(preSum, t)
		// 如果找不到则返回preSum的长度(n+1)
		if bound <= n {
			ans = Min(ans, bound - i)
		}
	}
	if ans == math.MaxInt32 {
		return 0
	}
	return ans
}